Trước khi người Tây Ban Nha đến, thành phố Cebu là bộ phận của một vương quốc trên đảo Cebu, vương quốc này là một trung tâm buôn bán và nay được gọi là Vương quốc Cebu. Thành phố do một hoàng tử của Vương triều Chola thành lập, ông là người lai Mã Lai và Tamil, có tên là Sri Lumay. Tên gọi Sugbu (dạng ngắn của Kang Sri Lumaying Sugbu) ám chỉ chiến thuật tiêu thổ của Sri Lumay chống lại những kẻ tấn công Moro theo Hồi giáo (Magalos).[7][8]

Ngày 7 tháng 4 năm 1521, nhà thám hiểm người Bồ Đào Nha Ferdinand Magellan đổ bộ tại Cebu. Ông được Quốc vương Rajah Humabon hoan nghênh. Tuy nhiên, Magellan sau đó bị giết trong trận Mactan ở hòn đảo gần thành phố Cebu, và các thành viên còn lại trong đoàn viễn chinh đã rời Cebu sau khi một vài người bị Humabon đầu độc do ông lo ngại sẽ bị ngoại bang xâm chiếm. Quân chủ cuối cùng của Sugbu trước khi Tây Ban Nha độ hộ là Rajah Tupas (mất năm 1565).[7][8]

Ngày 13 tháng 2 năm 1565, đoàn chinh phục của Tây Ban Nha dưới quyền Miguel López de Legazpi đến đảo Samar, sau đó chiếm lĩnh đảo này. Người Tây Ban Nha đến Cebu vào ngày 15 tháng 4 năm 1565, họ nỗ lực thương lượng với quân chủ địa phương là Rajah Tupas song nhận thấy người bản địa đã rời bỏ thị trấn. Rajah Tupas ra trình diện vào ngày 8 tháng 5, đảo Cebu trở thành thuộc địa của Tây Ban Nha. Hiệp ước Cebu được chính thức hoá vào ngày 3 tháng 7 năm 1565. Đoàn của López de Legazpi đặt tên cho thành phố là "Villa de San Miguel de Cebú" (về sau đổi thành "Ciudad del Santísimo Nombre de Jesús)." Năm 1567, đồn Cebu được củng cố khi có thêm 2.100 binh sĩ đến từ Tân Tây Ban Nha (Mexico).[9] Thuộc địa ngày càng phát triển và sau đó có thêm pháo đài San Pedro.

Đến năm 1569, khu định cư của người Tây Ban Nha tại Cebu trở nên quan trọng do là một cảng an toàn cho tàu thuyền từ Mexico và là một điểm xuất phát để khám phá thêm quần đảo. Một số đoàn viễn chinh quy mô nhỏ dưới quyền Juan de Salcedo đã đến Mindoro và Luzon, tại đó ông và Martín de Goiti giữ vai trò đứng đầu trong việc khuất phục các vương quốc Tundun và Seludong vào năm 1570. Một năm sau đó, López de Legazpi rời Cebu đi thảo luận về một hoà ước với các quân chủ bị đánh bại. Năm 1571, người Tây Ban Nha cho tăng cường bộ binh từ Mexico, tập hợp một đội quân gồm các chiến binh người Visayas cải sang Cơ Đốc giáo đến từ Cebu và Iloilo cùng với các thương nhân đến từ khu vực Tagalog, và tấn công Vương quốc Brunei.

Ngày 3 tháng 4 năm 1898, các nhà cách mạng địa phương dưới sự lãnh đạo của Leon Kilat đã khởi nghĩa chống lại nhà cầm quyền thực dân Tây Ban Nha và nắm quyền kiểm soát trung tâm đô thị sau ba ngày giao tranh. Cuộc khởi nghĩa kết thúc khi Leon Kilat bị ám sát và binh sĩ chính quyền được tăng viện từ Iloilo.[10] Ngày 26 tháng 12 năm 1898, chính quyền thực dân Tây Ban Nha cho rút binh sĩ đến Zamboanga, chuyển giao tài sản chính phủ cho Pablo Mejia.[11] Ngày sau đó, một chính quyền cấp tỉnh được thành lập với chủ tịch là Luis Flores.

Sau khi ký kết Hiệp định Paris (1898) kết thúc Chiến tranh Tây Ban Nha–Mỹ, Philippines được nhượng lại cho Hoa Kỳ. Ngày 21 tháng 2 năm 1899, USS Petrel (PG-2) triển khai một toán đổ bộ gồm 40 lính lên bờ biển Cebu.[12] Việc chuyển giao Cebu cho chính phủ Thịnh vượng chung được Luis Flores ký kết, song nhiều người khác tiến hành kháng cự cho đến năm 1901.[13] Thống đốc W. H. Taft đến Cebu vào ngày 17 tháng 4 năm 1901, và bổ nhiệm Julio Llorento làm thống đốc đầu tiên của tỉnh.[14] Juan Climaco được bầu nắm giữ chức vụ này vào năm 1904.[14]

Cebu là thị trấn từ khi thành lập vào năm 1565, và được nâng cấp là thành phố vào ngày 24 tháng 2 năm 1937. Nhiều thành phố khác của Philippines như Dansalan (nay là Marawi), Iloilo và Bacolod cũng được hình thành cùng thời điểm.

Cùng với phần còn lại của Philippines, Cebu bị người Nhật chiếm đóng trong Chiến tranh thế giới thứ hai. Người Nhật gặp phải kháng cự từ các du kích và lực lượng không chính quy tại địa phương. Cebu được giải phóng vào tháng 3 và tháng 4 năm 1945.